package UnitTest;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Auther: dingtian
 * @Date: 20-2-22 10 51
 * @Description: N皇后问题
 */
public class Nqueens {

    public static void main(String[] args) {
        int n = 8;
        Nqueens nqueens = new Nqueens();
        List<List<String>> solution = nqueens.solution(n);
        solution.forEach(lists -> System.out.println(lists));
    }

    public List<List<String>> solution(int n) {
        List<List<String>> res = new ArrayList<>();
        char[][] broad = new char[n][n];
        for (int i = 0; i < broad.length; i++) {
            Arrays.fill(broad[i], '.');
        }
        for (int i = 0; i < n; i++) {
            helper(res, broad, 0, n);
        }
        return res;
    }

    public void helper(List<List<String>> res, char[][] solution, int index,int n) {
        if (index >= n && checkNqueens(solution, n)) {
            res.add(getRes(solution, n));
            return;
        }
        for (int i = 0; i < n; i++) {
            if (isVaild(solution, index, i, n)) {
                solution[index][i] = 'Q';
                helper(res, solution, index + 1, n);
            }
        }
        if (index > 0) {
            Arrays.fill(solution[index - 1], '.');
            Arrays.fill(solution[index], '.');
        }
        return;
    }

    private boolean checkNqueens(char[][] solution, int n) {
        for (int i = 0; i < n; i++) {
            String row = new String(solution[i]);
            if (!row.contains("Q")) {
                return false;
            }
        }
        return true;
    }

    private List<String> getRes(char[][] solution, int n) {
        List<String> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            char[] row = solution[i];
            list.add(new String(row));
        }
        return list;
    }


    public boolean isVaild(char[][] solution, int y, int x,int n) {
        if (y >= 0 && x >= 0 && y <n &&x<n) {
            for (int j = y-1, i = x-1; j >= 0 && i >= 0; j--, i--) {
                if (solution[j][i] == 'Q') {
                    return false;
                }
            }
            for (int j = y-1, i = x+1; j >= 0 && i < n; j--, i++) {
                if (solution[j][i] == 'Q') {
                    return false;
                }
            }
            for (int j = y-1; j >= 0; j--) {
                if (solution[j][x] == 'Q') {
                    return false;
                }
            }
        }
        return true;
    }
}
